Block ciphers are algorithms that transform a specified-length block of plaintext input bits into another block of ciphertext output bits (or vice versa) deterministically based on a secret encryption key, and are typically used in various cryptographic systems or protocols. Examples of protocols that use block ciphers are the Data Encryption Standard (DES), the Advanced Encryption Standard (AES). CLEFIA (named after the French word “clef” meaning “key”), and Camellia, among many others.
Popular block ciphers have been implemented using various computer programming languages and are run in many computing environments. Block ciphers commonly encrypt input plaintext into encrypted output by performing one or more transformations (e.g., substitution or permutation) in a series of iterations (“rounds”). Some implementations of block ciphers employ lookup tables of computed values instead of or in addition to transformations to speed performance. The implementation details of a block cipher, along with the characteristics of the block cipher's design, can affect both its performance and its cryptographic security.
Cryptographers routinely analyze such block ciphers for vulnerabilities that could reveal information about the secret key in less time than a brute force attack. Discovery of the secret key—or portions of it—can compromise the encryption. Attempts to gain information about the secret key by focusing on the implementation of a block cipher are called side channel attacks. Cache timing attacks are a kind of side channel attack that can be effective against implementations of block ciphers that employ lookup tables of computed values.
Cache timing attacks take advantage of computing architectures that use a processor cache, which is a relatively small data storage region often located close to the computer's processor. Reading data from a cache is much faster than reading from main memory. Information read from main memory—such as lookup table data—is temporarily held in the processor cache, thereby providing quick access during the block cipher encryption algorithm. When the processor requests lookup table data that is already in the cache (a “cache hit” or “collision”), the processor's performance is generally better than when the processor requests lookup table data that is not in the cache (a “cache miss”). After a cache miss, the processor transfers the requested data from main memory to the cache, replacing other data stored in the caches but not recently used. Different processor architectures may have, e.g., caches of different total size, line size, and associativity; different replacement policies; and/or more than one level of hierarchical cache. In various computing architectures, caches may be shared by more than one processor.
Cache timing attacks manipulate or measure the contents of a shared memory cache to determine or affect the timing of lookups during an encryption operation or a series of encryption operations. For example, it typically takes longer for data to be retrieved from main memory than from the cache. Thus, if an attacker can carefully observe and analyze an encryption operation (e.g., the time required to encrypt a particular plaintext, or the effect on encryption time of evicting certain data from the cache), the attacker may be able to deduce information about the key being used. Cloud computing systems having virtual machines running on shared hardware provide a potential avenue for such attacks. Such attacks pose a significant concern because they do not require sophisticated equipment and do not require the attacker's physical proximity, thereby facilitating remote attacks that the victim may be unable to detect.
Previously proposed approaches to blunt the effectiveness of side channel attacks include modifications to processor hardware, changing a block cipher's requirements, slowing down all block cipher lookup operations to hide the differences between cache hits and cache misses, and not using lookup tables larger than one cache line (e.g., 64 bytes). It remains a challenge, however, to find a more universal approach to reduce exposure of block ciphers and processor architectures to cache timing attacks that does not require the redesign of either the block ciphers or the processor architectures and that does not necessarily entail a performance penalty.
Unless otherwise indicated herein, the materials described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.